package Mysinglelist3;

public class test1 {
    public static mysinglelist.ListNode merge(mysinglelist.ListNode headA, mysinglelist.ListNode headB) {
        mysinglelist.ListNode newHead = new mysinglelist.ListNode();
        mysinglelist.ListNode current = newHead;

        while (headA != null && headB != null) {
            if (headA.val >= headB.val) {
                current.next = headB;
                headB = headB.next;
                current = current.next;

            } else {
                current.next = headA;
                headA = headA.next;
                current = current.next;
            }
        }
        if (headA != null) {
            current.next = headA;
        }
        if (headB != null) {
            current.next = headB;
        }
        return newHead.next;
    }

    //判断链表的回文结构
    public static boolean huiwen(mysinglelist.ListNode Head) {
        //第一步，找到中间节点
        mysinglelist.ListNode fast = Head;
        mysinglelist.ListNode slow = Head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //第二步，翻转中间节点往后的链表
        mysinglelist.ListNode cur = slow.next;
        while (cur != null) {
            mysinglelist.ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //第三步，双指针一头一尾判断是否为回文
        while (Head != slow) {
            if (Head.val != slow.val) {
                return false;
            }
            //这里是为偶数链表准备的
            if (Head.next == slow) {
                return true;
            }
            Head = Head.next;
            slow = slow.next;

        }
        return true;
    }

    //找到两个链表的中间结点
    public static mysinglelist.ListNode getIntersectionNode(
            mysinglelist.ListNode headA, mysinglelist.ListNode headB) {

        mysinglelist.ListNode curA = headA;
        mysinglelist.ListNode curB = headB;

        int size1 = getsize(headA);
        int size2 = getsize(headB);
        int n = size1 - size2;
        if (n >= 0) {
            while (n != 0) {
                curA = curA.next;
                n--;
            }
        } else {
            while (n != 0) {
                curB = curB.next;
                n--;
            }
        }
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;


    }

    //创建一个交叉链表,还不完整，只是为了验证其他方法
    public static void getIntersectionList(
            mysinglelist.ListNode headA, mysinglelist.ListNode headB) {

        headA.next.next = headB.next.next;

    }

    //创建一个带环的链表
    public static void createLoopList(mysinglelist.ListNode head){
        mysinglelist.ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next;
    }


    public static int getsize(mysinglelist.ListNode node) {
        int count = 0;
        while (node != null) {
            node = node.next;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
//        mysinglelist list = new mysinglelist();
//        list.creatList();
//        list.show();

//        mysinglelist.ListNode newnode = list.reverseList();
//        list.show(newnode);

//        mysinglelist.ListNode midnode = list.getmidnode();
//        System.out.println(midnode.val);

//        mysinglelist.ListNode getrevknode = list.getrevknode(7);
//        System.out.println(getrevknode.val);

        mysinglelist list1 = new mysinglelist();
        list1.addEnd(10);
        list1.addEnd(20);
        list1.addEnd(30);
        list1.addEnd(30);

        list1.addEnd(40);



        mysinglelist list2 = new mysinglelist();
        list2.addEnd(20);
        list2.addEnd(40);
        list2.addEnd(60);
        list2.addEnd(80);
        list2.addEnd(100);

//        mysinglelist.ListNode merge = merge(list1.head, list2.head);
//        list1.show(merge);
//        mysinglelist.ListNode partition = list1.partition(list1.head, 30);
//        list1.show(partition);
//        System.out.println(huiwen(list1.head));
//        getIntersectionList(list1.head, list2.head);
//        mysinglelist.ListNode intersectionNode = getIntersectionNode(list1.head, list2.head);
//        System.out.println(intersectionNode.val);
//        createLoopList(list1.head);
//        System.out.println(list1.isCycle());
        list1.show();
        mysinglelist.ListNode del = list1.del();
        list1.show(del);
    }
}
